package recfun
import common._
import collection.immutable._

object Main {
  def main(args: Array[String]) {
    println("Pascal's Triangle")
    for (row <- 0 to 10) {
      for (col <- 0 to row)
        print(pascal(col, row) + " ")
      println()
    }
  }

  /**
   * Exercise 1
   */
  def pascal(c: Int, r: Int): Int = {
    if (c == 0 || c == r) {
      1
    } else {
      pascal(c - 1, r - 1) + pascal(c, r - 1)
    }
  }

  /**
   * Exercise 2
   */
  def balance(chars: List[Char]): Boolean = {
    def loop(chars: List[Char], stack: Stack[Char]): Boolean = {
      if (chars.isEmpty && stack.isEmpty) true
      else if (chars.isEmpty) false
      else {
        val c: Char = chars.head
        if (c == '(') {
          loop(chars.tail, stack.push(c))
        } else if (c == ')' && !stack.isEmpty && stack.top == '(') {
          loop(chars.tail, stack.pop)
        } else if (c == ')') {
          loop(chars.tail, stack.push(c)) //Could return false here, but that generates warning.
        } else
          loop(chars.tail, stack)
      }
    }
    loop(chars, Stack[Char]())
  }

  /**
   * Exercise 3
   *
   * If money is 0, that is 1 way to make change.
   * If money is less than 0, there are 0 ways to make change.
   * If amount of coins is 0, there are 0 ways to make change.
   */
  def countChange(money: Int, coins: List[Int]): Int = {
    def loop(money: Int, coins: List[Int]): Int = {
      if (money == 0) 1
      else if (money < 0) 0
      else if (coins.length == 0) 0
      else loop(money, coins.tail) + loop(money - coins.head, coins)
    }
    loop(money, coins)
  }
}
